package uestc.lj.basicPromotion.monstack;

import java.util.Stack;

/**
 * 数组中累积和与最小值的乘积，假设叫做指标A。
 * 给定一个数组，请返回子数组中，指标A最大的值。
 *
 * @Author:Crazlee
 * @Date:2021/11/27
 */
public class Code02_AAllTimesMinToMax {
	public static int getMax(int[] array) {
		int length = array.length;
		int[] sum = new int[length];
		sum[0] = array[0];
		//子数组的前缀和
		for (int i = 1; i < length; i++) {
			sum[i] = sum[i - 1] + array[i];
		}
		//全局最大指标值
		int max = Integer.MIN_VALUE;
		//单调递增栈
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < length; i++) {
			while (!stack.isEmpty() && array[stack.peek()] >= array[i]) {
				int popIndex = stack.pop();
				int leftIndex = stack.isEmpty() ? -1 : stack.peek();
				max = Math.max(max, leftIndex == -1 ? sum[i - 1] : (sum[i - 1] - sum[leftIndex]) * array[popIndex]);
			}
			stack.push(i);
		}
		while (!stack.isEmpty()) {
			int popIndex = stack.pop();
			max = Math.max(max,
					(stack.isEmpty() ? sum[length - 1] : (sum[length - 1] - sum[stack.peek()])) * array[popIndex]);
		}
		return max;
	}
}
